package zuochengyun;

import list.ListNode;

public class ListSelectionSort {

	
	public ListNode selectionSort(ListNode head){
		if(head == null || head.next == null){
			return head;
		}
		ListNode tail = null;   //排序部分的尾部
		ListNode front = head;  //未排序部分的头部
		ListNode smallPre = null;  //对于最下值结点在未排序部分的前一个结点
		ListNode small = null;  //最小的结点
		while(front != null){
			small = front;
			smallPre = getSmallestNode(front);
			if(smallPre != null){
				small = smallPre.next;  //small指向最小值
				smallPre.next = small.next;  //将small从未排序的断开
			}
			if(tail == null){
				head = small;  //更新head值
			}else{
				tail.next = small;
			}
			tail = small;
			//如果front等于small，就将front移动到下一个，否则不动
			front = front == small ? front.next : front;
		}
		return head;
	}
	
	/**
	 * @param node
	 * @return 返回的是最小值结点的前一个结点
	 */
	private ListNode getSmallestNode(ListNode node){
		if(node == null || node.next == null){
			return node;
		}
		ListNode res = null;
		ListNode pre = node;
		node = node.next;
		int min = Integer.MAX_VALUE;
		while(node != null){
			if(node.val < min){
				res = pre;
			}
			pre = node;
			node = node.next;
		}
		return res;
	}
}
